package com.dbh.alg.algorithm.hot100.二叉树;

import com.dbh.alg.algorithm.hot100.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Leetcode114_二叉树展开为链表 {

    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode current = root;
        while(current != null || !stack.isEmpty()) {
            if(current != null) {
                 list.add(current);
                 stack.push(current);
                 current = current.left;
            } else {
                TreeNode pop = stack.pop();
                current = pop.right;
            }
        }
        for (int i = 1; i < list.size(); i++) {
            TreeNode prev = list.get(i - 1);
            TreeNode curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }
}
